import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class J20230305LeetCode {
    public class TreeNode {
        int val;
        J20230305LeetCode.TreeNode left;
        J20230305LeetCode.TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, J20230305LeetCode.TreeNode left, J20230305LeetCode.TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int peakIndexInMountainArray(int[] arr) {
        int left=1;
        int right=arr.length-2;
        int ans=0;
        while (left<=right){
            int mid=(left+right)/2;
            if(arr[mid]>arr[mid+1]){
                ans=mid;
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return ans;
    }
    //前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer>res=new ArrayList<>();
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
    //中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>res=new ArrayList<>();
        preorder1(root,res);
        return res;
    }
    public void preorder1(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder1(root.left, res);
        res.add(root.val);
        preorder1(root.right, res);
    }
    //后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>res=new ArrayList<>();
        preorder2(root,res);
        return res;
    }
    public void preorder2(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder2(root.left, res)
        ;preorder2(root.right, res);
        res.add(root.val);
    }


    //二分法练习
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }



    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public int countNegatives(int[][] grid) {
        if(grid.length==0||grid[0].length==0){
            return 0;
        }
        int count=0;
        for (int i = 0, j = grid[0].length - 1; i < grid.length && j >= 0;) {
            if(grid[i][j]>=0){
                i++;
            }else{
                count+=grid.length-i;
                j--;
            }
        }
        return count;
    }

    public int findTheDistanceValue1(int[] arr1, int[] arr2, int d) {
        int cur=0;
        for (int i:arr1) {
            boolean ok=true;
            for (int j:arr2) {
                ok=ok&Math.abs(i-j)>d;
            }
            cur+=ok?1:0;
        }
        return cur;
    }
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int cnt = 0;
        for (int x : arr1) {
            int p = binarySearch(arr2, x);
            boolean ok = true;
            if (p < arr2.length) {
                ok &= arr2[p] - x > d;
            }
            if (p - 1 >= 0 && p - 1 <= arr2.length) {
                ok &= x - arr2[p - 1] > d;
            }
            cnt += ok ? 1 : 0;
        }
        return cnt;
    }

    public int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        if (arr[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public int findKthPositive(int[] arr, int k) {
        if(arr[0]>k){
            return k;
        }
        int l=0;
        int r=arr.length;
        while (l<r){
            int mid = (l + r) >> 1;
            int x = mid < arr.length ? arr[mid] : Integer.MAX_VALUE;
            if(x-mid-1>=k){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];
    }

    public int findKthPositive1(int[] arr, int k) {
        int missCount = 0, lastMiss = -1, current = 1, ptr = 0;
        for (missCount = 0; missCount < k; ++current) {
            if (current == arr[ptr]) {
                ptr = (ptr + 1 < arr.length) ? ptr + 1 : ptr;
            } else {
                ++missCount;
                lastMiss = current;
            }
        }
        return lastMiss;
    }

    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0,j=n-1; i <j; i++,j--) {
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        for (int i = 1; i <=n ; i++) {
            if(nums[i-1]>=i&&(i==n||nums[i]<i)){
                return i;
            }
        }
        return -1;
    }

    public int specialArray1(int[] nums) {
        for(int i=0;i<=nums.length;i++){
            int count=0;
            for(int j=0;j<nums.length;j++){if(nums[j]>=i){count++;}}
            if(count==i){return i;}
        }
        return -1;
    }


}
